package com.lfg.other;

import com.alibaba.fastjson.JSON;

public class CopyBook {


    public static void main(String[] args) {
        int ret = copy(new int[]{9, 3}, new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9});
        System.out.println("[" + JSON.toJSONString(ret) + "]");


        int ret2 = copy(new int[]{1, 2, 3}, new int[]{4, 5, 6});
        System.out.println("[" + JSON.toJSONString(ret2) + "]");
        // 6 15  9
    }

    public static int copy(int[] array1, int[] array2) {

        //m是书的个数，k是人的个数
        int m = array1[0];
        int k = array1[1];

        int[] sum = new int[m + 1];
        int[][] f = new int[k + 1][m + 1];//设用二维数组f[i][j]表示前i个人抄前j本书的用时最小值

        for (int i = 1; i <= m; i++) {
            sum[i] = sum[i - 1] + array2[i - 1];
        }


        for (int i = 1; i <= m; i++) {
            f[1][i] = sum[i];    //初始化下面循环中i等于1的情况，此时只有一个人，所用时间就是抄全部书的时间
        }

        for (int i = 1; i <= k; i++) {
            f[i][1] = sum[1];    //初始化下面循环中j等于1的情况，此时只有一本书，来多少人都是抄一本书的时间
        }


        for (int i = 2; i <= k; i++) {
            for (int j = 2; j <= m; j++) {
                f[i][j] = sum[j];
                for (int k1 = 2; k1 <= j; k1++) { // 第K本书开始copy
                    //1, 2, 3, 4, 5, 6, 7, 8, 9
                    f[i][j] = Math.min(f[i][j], Math.max(f[i - 1][k1 - 1], sum[j] - sum[k1 - 1]));
                }
            }
        }

        for (int i = m; i > 0; i--) {
            if (sum[m - 1] - sum[i - 1] > f[k][m]){
                //为了输出第一项，也就是第一个人从第一本开始抄的情况，需要让i=0进入循环，输出自然是从i+1开始的
                System.out.println(i + "-" + f[k][m]);
                break;//为了满足正序输出，但是是倒序循环，所以应该先递归后输出
            }
        }
        return f[k][m];
    }


}


//
// 11 16  = 4